#include <stdio.h>
#include <stdlib.h>
#define INF 9999999
#define MAXSIZE 500000 

typedef struct node1{
	int data;
	int weight;
	struct node1*next;
}Adj;

typedef int STACK;

typedef struct node3{
    int data;
	int pre;	
}QUEUE;

int* DFS(int u, int v);
int* BFS(int u, int v);
int* Dijkstra(int u, int v);

Adj* G[MAXSIZE];

int* shortestPath(int u, int v, const char algorithm[], const char name[]){
	int* path;
	Adj* newnode;
	int i;
	for(i = 0; i < MAXSIZE; i++){
		G[i] = NULL;
	}
	FILE* fp1 = fopen(name, "rb");
	if(fp1 == NULL){
		printf("open error\n");
		exit(1);
	}
	int u1, v1, weight1;
	while(!feof(fp1)){
	    fscanf(fp1, "%d%d%d", &u1, &v1, &weight1); 
	    newnode = (Adj*)malloc(sizeof(Adj));
	    newnode->data = v1;
	    newnode->weight = weight1;
            newnode->next = G[u1];
            G[u1] = newnode;
	}
	if( *algorithm == 'D'){
	    if(*(algorithm+1) == 'F')
		path = DFS(u, v);
            else
		path = Dijkstra(u, v);
	}	
	else{
	    path = BFS(u, v);
	}
	fclose(fp1);
	return path;
}

int* DFS(int u, int v)
{
	Adj *p;
	STACK* st = (STACK*)malloc(MAXSIZE*sizeof(STACK));
	char* visited = (char*)malloc(MAXSIZE*sizeof(char));
	int i;
	for(i = 0; i < MAXSIZE; i++){
		visited[i] = 0;
	}
	
	int top = -1;
	top++;
	st[top] = u;
	visited[u] = 1;
	
	int process_point; 
	while(top != -1){
            process_point = st[top];
	    if(process_point == v){
		break;
	    }
	    p = G[process_point];
	    while(p != NULL){
		if(visited[p->data] == 0){
		    top++;
		    st[top] = p->data;
		    visited[p->data] = 1;
		    break;
		}
		p = p->next;
	    }
	    if(p == NULL){
		top--;
	    }
	}
	int *path =(int*)malloc(MAXSIZE*sizeof(int)); 
	int k = top;
	for(i = top; i > 0; i--){
		path[st[i]] = st[i-1];
	}
	path[st[0]] = -1;
	return path;
}

int* BFS(int u, int v)//SPFA
{
	Adj *p;
	int *path = (int*)malloc(MAXSIZE*sizeof(int));
	
	QUEUE *qu = (QUEUE*)malloc(MAXSIZE*sizeof(QUEUE));  
	int front = -1, rear = -1;
	
	int *dist = (int*)malloc(MAXSIZE*sizeof(int));
	int i;
	for(i = 0; i < MAXSIZE; i++){
	    dist[i] = INF;
	}
	
	rear++;
	qu[rear].data = u;
	dist[u] = 0;
	path[u] = -1;
	int process_point; 
	while(front != rear){
	    front++;
	    process_point = qu[front].data;
	    p = G[process_point];
	    while(p != NULL){
		if(dist[process_point] + p->weight < dist[p->data]){
		    int find;
		    int flag = 0; 
		    for(find = front+1; find <= rear; find++){
			if(qu[find].data == p->data){
			    flag = 1;
			    break;
		        }
		    }
		    if(flag == 1){
			break;
		    } 
		    else{
			rear++;
			qu[rear].data = p->data;
			dist[p->data] = dist[process_point] + p->weight;
			path[p->data] = process_point;
		    }
		}
		p = p->next;
	    }
	}
	return path;
}

int* Dijkstra(int u, int v)
{
	int i;
	int *dist = (int*)malloc(MAXSIZE*sizeof(int));
	char* s = (char*)malloc(MAXSIZE*sizeof(char));
        int* path = (int*)malloc(MAXSIZE*sizeof(int));
	for(i = 0; i < MAXSIZE; i++){
	    dist[i] = INF;
	    s[i] = 0;
	}
	
	dist[u] = 0;
	s[u] = 1;
	path[u] = -1; 
	
	Adj* p;
	p = G[u];
	while(p != NULL){
	    dist[p->data] = p->weight;
	    path[p->data] = u;
	    p = p->next;
	}
	
	int mindis,x;
	while(1){
	    if(s[v] == 1){
	        break;
	    }
	    mindis = INF;
	    for(i = 0; i < MAXSIZE; i++){
		if(s[i] == 0 && dist[i] < mindis){
		    mindis = dist[i];
		    x = i;
		}
	    }
	    s[x] = 1;
	    p = G[x];
	    while(p != NULL){
	        if(s[p->data] == 0 && dist[p->data] > dist[x] + p->weight){
		    dist[p->data] = dist[x] + p->weight;
		    path[p->data] = x;
		}
		p = p->next;
	    }
	}
	return path;
}
